The present invention relates to a traversal method in processing tree structure information, and in particular, to a traversal method and an apparatus using the same, the method being capable of increasing an efficiency of a traversal of a tree when evaluation of information of nodes constituting the tree prior to or during a tree traversal is difficult.
A method in which data of a tree structure is subjected to a traversal or scanned to effect processing based on information of nodes of the tree structure according to the sequence of the traversal of the nodes has often been employed in various software including a compiler.
The object data of the scanning or traversal constitutes, for example, as shown in FIG. 15, a tree structure 200 having nodes 201 as components thereof and branches 202 connecting nodes. Furthermore, among the nodes 201 of the tree structure, the nodes at the upper-most position is called a root and a node which is not connected to a node therebelow is referred to as a leaf. In addition, for the relationship between nodes 201 connected to each other by a branch 202, a node y connected to a node x and is located immediately therebelow is called a child of the node x, which is in turn referred to as a parent. Moreover, for the relationship of nodes sharing a parent, children on the left-hand and right-hand sides of the parent node x are respectively referred to as an elder child and a younger child, whereas a node on the right-hand side of the node x is named as a younger brother of the node x, which is accordingly referred to as the elder brother.
Incidentally, since these nodes configure a tree structure, each node retains the positions of data of the elder child and younger brother thereof. Furthermore, if there does not exist the elder child or the younger brother, a special value, nil is retained in place of the location thereof.
When effecting a traversal of a tree having such a structure, a depth-first-search is achieved, namely, starting from the root of the tree, the traversal is accomplished downward from the child at the left-most position. When all children of this sequence are completely searched, the similar search is executed from the child at the second left-most position. This operation is repeatedly effected toward the right-most location.
Furthermore, in a case where an operation is to be executed for each node during the search, there is used method in which the tree traversal is achieved in a sequence including all of a preorder in which the root is first processed for the operation for each node, an in order in which the root is processed at an intermediate point for the operation, and a post-order in which the root is finally processed, thereby sequentially arranging data according to the processing order.
For example, as shown in FIG. 16(a) a node R has three children. Applying the method above to the tree structure including sub-trees a-c to effect the tree traversal and to sequentially arrange data, there are sequentially attained in an arrangement a result R.sub.1 of the tree traversal (preorder) of the node R before the sub-trees a-c, a result R.sub.2 of the tree traversal (in order) of the node R between the sub-trees a and c, a result R.sub.3 of the tree traversal (in order) between the sub-trees b and c, and a result R.sub.4 of the tree traversal (postorder) of the node R after the sub-trees a-b.
As a consequence, in a tree traversal, the node assigned as an object of the tree traversal at present possesses states of which the number is expressed as the total of the children thereof +1. These states are referred to as traversal stages of the node and is represented by integers ranging from 0 to the total of the children thereof. Each node is provided with an attribute of each traversal stage, namely, contents R.sub.1 -R.sub.4 to be sequentially arranged or information indicating the contents R.sub.1 -R.sub.4.
The tree traversal method of this kind is particularly applied to cases, for example, a case where evaluation of the attributes of all nodes can be accomplished at a low cost prior to the start of the tree traversal or a case where although the evaluation of the respective attributes can be achieved according to the order of processing or visiting of nodes when the tree traversal is effected.
However, in a case where nodes are dependent on each other and hence the entire tree must undergo a tree traversal to evaluate attributes of a node or in a case where a great amount of information is required for the evaluation of the attribute and consequently the attributes of all nodes cannot be arranged through a tree traversal, the sequence of evaluation of attributes of each node is restricted. If the evaluation sequence does not agree with the tree traversal order on each node in the tree traversal, the respective operations cannot be achieved according to the method above.
For example, according to the method described in the "Algorithm+Data Structure=Program", N. Wirth (translated by Takuya Katayama), 1979, the Computer Association of Japan, the entire tree undergoes a tree traversal beginning from the root of the tree structure so as to effect processing according to the preorder, inorder, and postorder, respectively. As a consequence, in a case where the nodes to be processed or visited in a tree traversal are restricted, the tree traversal must be repetitiously accomplished for the entire tree including the nodes not to be processed in the pertinent tree traversal.
Furthermore, in such a method, when an attribute propagation occurs from a node to the descendant thereof, it is necessary to dispose a common area to store the entire information to be propagated and to refer to the information each time a search is carried out for a node, which disadvantageously necessitates a large common area.
According to the prior art technology, in a case where the nodes to be processed in a tree traversal are restricted, the entire tree is repeatedly subjected to the traversal, which leads to a problem that the processing efficiency is deteriorated.
Furthermore, such cases have not been taken into consideration as cases where processing of nodes associated with different processing objects causes an interference therebetween, for example, where the processing results of each node are to be sequentially arranged in a structure.
Moreover, considerations have not been given to a case associated with an occurrence of an attribute propagation from a node to the descendant thereof in which a timing of the generation of the propagation attribute at the node is different from a timing of evaluation of nodes of the descendance through reference to the propagation attribute.